package heap;

import java.util.PriorityQueue;

/**
 * 题目：数据流中的第k大的值
 * 题目详述 ：
 * 设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
 * 请实现 KthLargest类：
 * KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
 * int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
 */
public class KthLargest {
    /**
     * 核心思想：
     * 获取到数据集合中第k大元素值；
     * 1.使用排序数组
     * （1）即，需要将数据集合中所获取的元素放入到数组中，同时对于动态数组中的所有元素进行排序，
     *  时间复杂度：O（logn）
     *  空间复杂度：O（n）
     * （2）对于排序数组中新增数据元素的话，所需要消耗的时间复杂度：O（n）；
     *
     * 2.使用最小堆
     * 思路 ：
     * （1）首先，获取数据集合中的k个最大元素；
     * （2）将k个最大元素构建成最小堆的结构（即，堆顶元素为数据集合中k个最大元素中的最小值）
     * （3）当堆未满的时候，后续数据流中所读取的元素，直接插入最小堆中；
     * （4）但是，同时来说，若是堆满了的话，即需要将后续数据流中所读取的元素与堆顶元素进行比较，
     *  若是其大于对丁元素的话，说明数据流中新读取的元素为 k个最大元素中的一个
     */
    PriorityQueue<Integer> minHeap;
    Integer size;
    public KthLargest(int k, int[] nums) {
        // 最小堆大小
        size = k;
        // 初始化最小堆
        minHeap = new PriorityQueue<>();
        for (int num : nums) {
            // 初始化：将开始数据流中的数据集合（nums数组）进行读入
            add(num);
        }
    }

    public int add(int val) {
        if(minHeap.size() < size){
            // 若是最小堆的当前容量 < 最小堆的最大容量,直接将数据流中所读取的元素加入到最小堆中；
            minHeap.offer(val);
        }
        else if(val >= minHeap.peek() ){
            // 当数据流中所读取的元素 >= 最小堆中的堆顶元素，即说明数据流所读取的元素是此数据集合中k个最大元素中的一个元素；
            // 1.删除最小堆中的堆顶元素
            minHeap.poll();
            // 2.将数据流所读取的元素加入到最小堆中
            minHeap.offer(val);
        }
        // 所需要返回的结果 ：返回数据流中已经读取元素的第k大元素
        // （即，最小堆堆顶元素代表着数据集合中k个最大元素中的最小元素，即题目所选哟返回的数据流中已经读取元素的第k大元素）
        return minHeap.peek();
    }
    /**
     * 分析 ：
     * （1）空间复杂度：由于最小堆的最大容量为k个元素，空间复杂度：O（k）；
     * （2）时间复杂度：O（logk）；
     */
}
